﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <Windows.h>
#include <assert.h>
#include <limits.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdbool.h>
typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

// 初始化栈
void STInit(ST* pst);
// 销毁栈
void STDestroy(ST* pst);
// 添加数据
void STPush(ST* pst, STDataType x);
// 删除数据
void STPop(ST* pst);
// 弹出数据
STDataType STTop(ST* pst);
// 判断是否为空
bool STEmpty(ST* pst);
// 判断大小
int STSize(ST* pst);
// 初始化栈
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
// 销毁栈
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
// 添加数据
void STPush(ST* pst, STDataType x)
{
	if (pst->capacity == pst->top)
	{
		int newcapacity = (pst->capacity == 0 ? 4 : pst->capacity * 2);
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
// 删除数据
void STPop(ST* pst)
{
	assert(pst);
	assert(!(STEmpty(pst)));
	pst->top--;
}
// 弹出数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!(STEmpty(pst)));
	return pst->a[pst->top - 1];
}
// 判断是否为空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
// 判断大小
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead->next == NULL)
	{
		QNode* head = pq->phead;
		free(head);
		pq->phead = pq->ptail = NULL;
		pq->size = 0;
	}
	else
	{
		QNode* head = pq->phead;
		pq->phead = pq->phead->next;
		free(head);
		pq->size--;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return(pq->phead->data);
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}
//                       用栈实现队列
typedef struct {
	ST pushst;
	ST popst;
} MyQueue;

MyQueue* myQueueCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	if (obj == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	STInit(&(obj->pushst));
	STInit(&(obj->popst));
	return obj;
}

void myQueuePush(MyQueue* obj, int x) {
	assert(obj);
	STPush(&(obj->pushst), x);
}

int myQueuePop(MyQueue* obj) {
	assert(obj);
	if (!STEmpty(&(obj->popst)))
	{
		int tem = STTop(&(obj->popst));
		STPop(&(obj->popst));
		return tem;
	}
	while (!STEmpty(&(obj->pushst)))
	{
		STPush(&(obj->popst), STTop(&(obj->pushst)));
		STPop(&(obj->pushst));
	}
	int tem = STTop(&(obj->popst));
	STPop(&(obj->popst));
	return tem;

}
int myQueuePeek(MyQueue* obj) {
	assert(obj);
	if (STEmpty(&(obj->popst)))
	{
		while (!STEmpty(&(obj->pushst)))
		{
			STPush(&(obj->popst), STTop(&(obj->pushst)));
			STPop(&(obj->pushst));
		}
	}
	int tem = STTop(&(obj->popst));
	return tem;
}
bool myQueueEmpty(MyQueue* obj) {
	return (STEmpty(&(obj->pushst)) && STEmpty(&(obj->popst)));
}
void myQueueFree(MyQueue* obj) {
	STDestroy(&(obj->popst));
	STDestroy(&(obj->pushst));
	free(obj);
	obj = NULL;
}

//                       用队列实现栈
typedef struct {
	Queue q1;
	Queue q2;
} MyStack;
MyStack* myStackCreate() {
	MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));
	if (tmp == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	QueueInit(&(tmp->q1));
	QueueInit(&(tmp->q2));
	return tmp;
}
void myStackPush(MyStack* obj, int x) {
	if (!QueueEmpty(&obj->q1)) {
		QueuePush(&obj->q1, x);
	}
	else {
		QueuePush(&obj->q2, x);
	}
}
int myStackPop(MyStack* obj) {
	Queue* empty = &obj->q1;
	Queue* noempty = &obj->q2;
	if (!QueueEmpty(empty))
	{
		empty = &obj->q2;
		noempty = &obj->q1;
	}
	while (QueueSize(noempty) > 1)
	{
		QueuePush(empty, QueueFront(noempty));
		QueuePop(noempty);
	}
	int n = QueueFront(noempty);
	QueuePop(noempty);
	return n;
}
int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}
bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}

//                       设计循环队列
typedef struct {
	int front;
	int rear;
	int k;
	int* a;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->a = (int*)malloc(sizeof(int) * (k + 1));
	if (obj == NULL || obj->a == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	obj->k = k;
	obj->front = obj->rear = 0;
	return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
		return false;
	obj->a[obj->rear] = value;
	obj->rear++;
	obj->rear %= (obj->k + 1);
	return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return false;
	obj->front++;
	obj->front %= (obj->k + 1);
	return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

//bool isValid(char* s) {
//	ST st;
//	STInit(&st);
//	while (*s)
//	{
//		// 左括号入栈
//		if (*s == '(' || *s == '{' || *s == '[')
//		{
//			STPush(&st, *s);
//		}
//		// 右括号出栈匹配
//		else
//		{
//			if (STEmpty(&st))
//			{
//				STDestroy(&st);
//				return false;
//			}
//			else
//			{
//				char tmp = STTop(&st);
//				STPop(&st);
//				if (*s == ']' && tmp != '[' || *s == ')' && tmp != '(' || *s == '}' && tmp != '{')
//				{
//					STDestroy(&st);
//					return false;
//				}
//			}
//		}
//		++s;
//	}
//	bool ret = STEmpty(&st);
//	STDestroy(&st);
//	return ret;
//}
//int main()
//{
//	char s = "{(())}";
//	if (isValid(&s))
//	{
//		printf("yes");
//		return 1;
//	}
//	printf("0");
//	return 0;
//}
//struct Node {
//    int val;
//    struct Node* next;
//    struct Node* random;
//    };
//struct Node* copyRandomList(struct Node* head) {
//    struct Node* cur = head;
//    while (cur)
//    {
//        struct Node* copy = (struct Node*)malloc(sizeof(struct Node*));
//        copy->val = cur->val;
//        struct Node* next = cur->next;
//        cur->next = copy;
//        copy->next = next;
//        cur = next;
//    }
//    struct Node* cur = head;
//    while (cur)
//    {
//        struct Node* copye = cur->next;
//        if (cur->random == NULL)
//            copye->random = NULL;
//        else
//        {
//            copye->random = cur->random->next;
//        }
//        cur = copye->next;
//    }
//    struct Node* cophead = NULL, * coptail = NULL;
//    cur = head;
//    while (cur)
//    {
//        struct Node* copy = cur->next;
//        struct Node* next = copy->next;
//        if (coptail == NULL)
//        {
//            cophead = coptail = copy;
//        }
//        else
//        {
//            coptail->next = copy;
//            coptail = coptail->next;
//        }
//        cur->next = next;
//        cur = next;
//    }
//    return cophead;
//
//}

///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slou = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slou = slou->next;
//        if (slou == fast)
//        {
//            struct ListNode* meet = slou;
//            while (head != meet)
//            {
//                head = head->next;
//                meet = meet->next;
//            }
//            return meet;
//        }
//    }
//    return NULL;
//}



//struct ListNode
//{
//    int val;
//    struct ListNode* next;
//};
//// 单链表打印
//void SListPrint(struct ListNode* plist)
//{
//    struct ListNode* cur = plist;
//    while (cur != NULL)
//    {
//        printf("%d->", cur->val);
//        cur = cur->next;
//    }
//    printf("NULL\n");
//}
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slou = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slou = slou->next;
//        if (slou == fast)
//        {
//            struct ListNode* meet = fast;
//            struct ListNode* meetHead = meet->next;
//            //meet = NULL;
//            struct ListNode* heada = head;
//            struct ListNode* headb = meet->next;
//            meet->next = NULL;
//            SListPrint(head);
//            SListPrint(meetHead);
//            int lena = 1;
//            int lenb = 1;
//            while (heada->next)
//            {
//                heada = heada->next;
//                lena++;
//            }
//            while (headb->next)
//            {
//                headb = headb->next;
//                lenb++;
//            }
//            struct ListNode* longList = heada;
//            struct ListNode* shortList = headb;
//            if (lena < lenb)
//            {
//                longList = headb;
//                shortList = heada;
//            }
//            int k = abs(lena - lenb);
//            while (k--)
//            {
//                longList = longList->next;
//            }
//            while (longList != NULL && longList != shortList )
//            {
//                longList = longList->next;
//                shortList = shortList->next;
//            }
//            return meetHead;
//        }
//    }
//    return NULL;
//}
//int main()
//{
//    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n1);
//    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n2);
//    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n3);
//    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n4);
//    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n5);
//    struct ListNode* b1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(b1);
//    struct ListNode* b2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(b2);
//
//    n1->val = 3;
//    n2->val = 2;
//    n3->val = 0;
//    n4->val = -4;
//    //n5->val = 5;
//    //b1->val = 5;
//    //b2->val = 6;
//    n1->next = n2;
//    n2->next = n3;
//    n3->next = n4;
//    n4->next = n2;
//    //n5->next = NULL;
//    //b1->next = b2;
//    //b2->next = n2;
//    struct ListNode* head = n1;
//    struct ListNode* meet = detectCycle(head);
//    printf("%d", meet->val);
//    return 0;
//}
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slou = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slou = slou->next;
//        if (slou == fast)
//        {
//            return true;
//        }
//    }
//    return false;
//}

//struct ListNode
//{
//    int val;
//    struct ListNode* next;
//};
//// 单链表打印
//void SListPrint(struct ListNode* plist)
//{
//    struct ListNode* cur = plist;
//    while (cur != NULL)
//    {
//        printf("%d->", cur->val);
//        cur = cur->next;
//    }
//    printf("NULL\n");
//}
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* heada = headA;
//    struct ListNode* headb = headB;
//    int lena = 1;
//    int lenb = 1;
//    while (heada->next)
//    {
//        lena++;
//        heada = heada->next;
//    }
//    while (headb->next)
//    {
//        lenb++;
//        headb = headb->next;
//    }
//    if (heada != headb)
//    {
//        return NULL;
//    }
//    int k = abs(lena - lenb);
//    struct ListNode* longe = headA;
//    struct ListNode* shorte = headB;
//    if (lena < lenb)
//    {
//        longe = headB;
//        shorte = headA;
//    }
//    while (k--)
//    {
//        longe = longe->next;
//    }
//    while (longe != shorte)
//    {
//        longe = longe->next;
//        shorte = shorte->next;
//    }
//    return longe;
//}
//int main()
//{
//    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n1);
//    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n2);
//    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n3);
//    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n4);
//    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(n5);
//    struct ListNode* b1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(b1);
//    struct ListNode* b2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    assert(b2);
//
//    n1->val = 4;
//    n2->val = 1;
//    n3->val = 8;
//    n4->val = 4;
//    n5->val = 5;
//    b1->val = 5;
//    b2->val = 6;
//    n1->next = n2;
//    n2->next = n3;
//    n3->next = n4;
//    n4->next = n5;
//    n5->next = NULL;
//    b1->next = b2;
//    b2->next = n2;
//    SListPrint(n1);
//    SListPrint(b1);
//    struct ListNode* min = getIntersectionNode(n1, b1);
//    SListPrint(min);
//        
//    return 0;
//}


/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* rhead = NULL;
//    struct ListNode* cur = head;
//    while (cur) {
//        struct ListNode* next = cur->next;
//        cur->next = rhead;
//        rhead = cur;
//        cur = next;
//    }
//    return rhead;
//}
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* slow = head;
//    struct ListNode* fast = head;
//    while (fast != NULL && fast->next != NULL) {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//    return slow;
//}
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* head) {
//        struct ListNode* midhead = middleNode(head);
//        struct ListNode* rmid = reverseList(midhead);
//        {
//            while (rmid)
//            {
//                if (rmid->val != head->val)
//                {
//                    return false;
//                }
//                else
//                {
//                    rmid = rmid->next;
//                    head = head->next;
//                }
//            }
//            return true;
//        }
//    }
//};


//struct ListNode {
//    int val;
//    struct ListNode* next;
//
//}
//ListNode* partition(ListNode* pHead, int x) {
//    struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
//    lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
//    greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* cur = pHead;
//    while (cur)
//    {
//        if (cur->val < x)
//        {
//            lesstail->next = cur;
//            lesstail = lesstail->next;
//        }
//        else
//        {
//            greatertail->next = cur;
//            greatertail = greatertail->next;
//        }
//        cur = cur->next;
//    }
//    lesstail->next = greaterhead->next;
//    greatertail->next = NULL;
//    struct ListNode* head = lesshead->next;
//    free(greaterhead);
//    free(lesshead);
//    return(head);
//}


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* rhead = NULL;
//    struct ListNode* cur = head;
//    while (cur)
//    {
//        struct ListNode* next = cur->next;
//        cur->next = rhead;
//        rhead = cur;
//        cur = next;
//        if (next)
//            next = next->next;
//
//    }
//
//    return rhead;
//}

//struct ListNode {
//    int val;
//    struct ListNode* next;
//};
//
//
//
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//    struct ListNode* head = NULL;
//    struct ListNode* tail = NULL;
//    while (list1 && list2)
//    {
//        //取小的尾插
//        if (list1->val < list2->val)
//        {
//            if (tail == NULL)
//            {
//                head = tail = list1;
//            }
//            else
//            {
//                tail->next = list1;
//                tail = tail->next;
//            }
//            list1 = list1->next;
//        }
//        else
//        {
//            if (tail == NULL)
//            {
//                head = tail = list2;
//            }
//            else
//            {
//                tail->next = list2;
//                tail = tail->next;
//            }
//            list2 = list2->next;
//        }
//    }
//    if (list1)
//        tail->next = list1;
//    if (list2)
//        tail->next = list2;
//    return head;
//}
//class Point {
//public:
//    Point(int xx = 0, int yy = 0) {
//        X = xx;
//        Y = yy;
//    }
//    Point(Point& p) {
//        X = p.X;
//        Y = p.Y;
//        cout << "*";
//    }
//private:
//    int X, Y;
//};
//
//class Line {
//public:
//    Line(Point xp1, Point xp2) : p1(xp1), p2(xp2) {}
//private:
//    Point p1, p2;
//};



//
//struct ListNode 
//{
//    int val;
//    struct ListNode* next;
//};
// 

//
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    struct ListNode* prev = NULL,
//    struct ListNode* cur = head;
//    while (cur)
//    {
//        if (cur->val != val)
//        {
//            prev = cur;
//            cur = cur->next;
//        }
//        else
//        {
//            //相等的时候，要删除
//        }
//    }
//    return head;
//}


//     //2.删除排序数组中的重复项
//int removeDuplicates(int* nums, int numsSize) {
//    if (numsSize == 0) {
//        return 0;
//    }
//    int fast = 1, slow = 1;
//    while (fast < numsSize) {
//        if (nums[fast] != nums[fast - 1]) {
//            nums[slow] = nums[fast];
//            ++slow;
//        }
//        ++fast;
//    }
//    return slow;
//}

//bool canConstruct(char* ransomNote, char* magazine) {
//    int i, j, n = 0;
//    int flag = 0;
//    int len1 = strlen(ransomNote);
//    int len2 = strlen(magazine);
//    if (len1 > len2)
//    {
//        return false;
//    }
//    for (i = 0; i < len1; i++)
//    {
//        flag = 0;
//        for (j = 0; j < len2; j++)
//        {
//            if (ransomNote[i] == magazine[j])
//            {
//                flag = 1;
//                for (int a = j; a < len2; a++)
//                {
//                    magazine[a] = magazine[a + 1];
//                }
//                len2--;
//            }
//        }
//        if (flag == 0)
//        {
//            return false;
//        }
//    }
//    if (flag == 1)
//    {
//        return true;
//    }
//}
//int main()
//{
//
//    return 0;
//}


////dayin 零星      day 5 2023/3/8
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	for (int i=0;i<n;i++)
//	{
//		for (int j = n-1-i; j >= 0; j--)
//		{
//			printf(" ");
//		}
//		for
//	}
//	return 0;
//}


/*
思路：
仔细观察图形，可以发现，此图形中是由空格和*按照不同个数的输出组成的。
上三角：先输出空格，后输出*，每行中
  空格：从上往下，一行减少一个
  *：2*i+1的方式递增

下三角：先输出空格，后输出*，每行中
  空格：从上往下，每行多一个空格
  *： 从上往下，按照2*(line-1-i)-1的方式减少，其中：line表示总共有多少行
按照上述方式，将上三角和下三角中的空格和*分别输出即可。
*/

//
//int main()
//{
//	int line = 0;
//	int i = 0;
//	scanf("%d", &line);//7
//	//打印上半部分
//	for (i = 0; i < line; i++)
//	{
//		//打印一行
//		//打印空格
//		int j = 0;
//		for (j = 0; j < line - 1 - i; j++)
//		{
//			printf(" ");
//		}
//		//打印*
//		for (j = 0; j < 2 * i + 1; j++)
//		{
//			printf("*");
//		}
//		printf("\n");
//	}
//
//
//	//打印下半部分
//	for (i = 0; i < line - 1; i++)
//	{
//		//打印一行
//		int j = 0;
//		for (j = 0; j <= i; j++)
//		{
//			printf(" ");
//		}
//		for (j = 0; j < 2 * (line - 1 - i) - 1; j++)
//		{
//			printf("*");
//		}
//		printf("\n");
//	}
//	return 0;
//}


////      day4  2023/3/7                                                                    字符串逆序
//void reverse_str(char* str)   //传的地址要解引用一下
//{
//	assert(str);  //判断str是不是空字符串
//	int len = strlen(str);
//	char* left = str;
//	char* right = str + len - 1;
//	while (left < right)
//	{
//		char tmp = *left;
//		*left = *right;
//		*right = tmp;
//		left++;
//		right--;
//	}
//}
//int main()
//{
//	char arr[10001];
//	//输入
//	gets(arr);
//	//int sz = strlen(arr);
//	printf("%s\n", arr);
//	//逆序
//	reverse_str(arr);
//	printf("%s\n", arr);
//	return 0;
//}





////        day3  2023/3/6
////编写代码，演示多个字符从两端移动，向中间汇聚
//int main()
//{
//	char arr1[] = "hellow world!";
//	char arr2[] = "*************";
//	int lift = 0;
//	int right = strlen(arr1) - 1;
//	while (lift <= right)
//	{
//		Sleep(500);
//		arr2[lift] = arr1[lift];
//		arr2[right] = arr1[right];
//		lift++;
//		right--;
//		printf("%s\n", arr2);
//		Sleep(300);
//		system("cls");
//
//	}
//	printf("%s\n", arr2);
//	return 0;
//}




////********* day2 2023/3/5        三角形
//// 
//// KiKi想知道已经给出的三条边a，b，c能否构成三角形，如果能构成三角形，判断三角形的类型（等边三角形、等腰三角形或普通三角形）
//// 
//int main()
//{
//	int a, b, c;
//	scanf("%d %d %d", &a, &b, &c);
//	if (a + b < c || a + c < b || b + c < a)
//		printf("%d  %d  %d构不成三角形", a ,b ,c);
//	else
//	{
//		if (a == b && b == c && a==c)
//			printf("%d  %d  %d构成了等边三角形", a, b, c);
//		else if (a == b || b == c || a==c)
//			printf("%d  %d  %d构成了等腰三角形", a, b, c);
//		else
//			printf("%d  %d  %d 可以构成三角形", a, b, c);
//	}
//	return 0;
//}





////           
////********* day1 2023/3/4        冒泡排序
////
//void bubble_short(int arr[], int sz)   //冒泡排序函数
//{
//	int i = 0;//控制冒泡排序的趟数
//	int temp = 1;  //优化方案：假设已经是升序
//	for (i = 0; i < sz; i++)
//	{
//		//int temp = 1;
//		int j = 0;    //冒泡排序的过程
//		for (j = 0; j < sz - 1 - i; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				int tmp = arr[j];
//				arr[j] = arr[j + 1];
//				arr[j + 1] = tmp;
//				temp = 0;   //temp==0  
//			}
//		}
//		if (temp)
//			break;		
//	}
//}
//print(int arr[], int sz)    //打印数组的每个元素
//{
//	int i = 0;
//	for (i = 0; i < sz; i++)
//		printf("%d ", arr[i]);
//	printf("\n");
//}
//int main()
//{
//	int arr[10] = { 9,6,7,5,8,4,1,0,2,3 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	printf("排序前：---> ");
//	print(arr, sz);
//	bubble_short(arr, sz);
//	printf("排序后----> ");
//	print(arr, sz);
//	return 0;
//}

//   day 6 3/8 判断矩阵是否相等
//int main()
//{
//	int arr1[10][10];
//	int arr2[10][10];
//	int m, n, i, j;
//	int test = 1;
//	scanf("%d %d", &m, &n);
//	for (i = 0; i < m; i++)
//	{
//		for (j = 0; j < n; j++)
//		{
//			scanf("%d ", arr1[i][j]);
//		}
//	}
//	for (i = 0; i < m; i++)
//	{
//		for (j = 0; j < n; j++)
//		{
//			scanf("%d ", arr2[i][j]);
//		}
//	}
//	for (i = 0; i < m; i++)
//	{
//		for (j = 0; j < n; j++)
//		{
//			if (arr1[i][j] != arr2[i][j])
//			{
//				test = 0;
//				break;
//			}
//		}
//		if (test == 0)
//			break;
//	}
//	if (test == 0)
//		printf("No");
//	if (test == 1)
//		printf("Yes");
//	return 0;
//}




//   day 7 3/9  


// KiKi想获得某年某月有多少天，请帮他编程实现。输入年份和月份，计算这一年这个月有多少天。
//输入描述：
//多组输入，一行有两个整数，分别表示年份和月份，用空格分隔。
//int runnian(int year)
//{
//	if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//		return 1;
//	else
//		return 0;
//}
//int main()
//{
//	int year,mon;
//	while (scanf("%d %d", &year,&mon) != EOF)
//	{
//		if (mon > 12 || mon < 1)
//			printf("输入错误，请重新输入\0");
//		else
//		{
//			if (mon == 2)
//			{
//				if (runnian(year))
//					printf("%d", 29);
//				else
//					printf("%d", 28);
//			}
//			else
//			{
//				if (mon == 1 || mon == 3 || mon == 5 || mon == 7 || mon == 8 || mon == 10 || mon == 12)
//				{
//					printf("31\n");
//				}
//				else if (mon == 4 || mon == 6 || mon == 9 || mon == 11)
//				{
//					printf("30\n");
//				}
//			}
//		}
//	}
//	return 0;
//}



//////KiKi非常喜欢网购，在一家店铺他看中了一件衣服，他了解到，如果今天是“双11”（11月11日）则这件衣服打7折，“双12” （12月12日）则这件衣服打8折，
//////如果有优惠券可以额外减50元（优惠券只能在双11或双12使用），求KiKi最终所花的钱数。
/*一行，四个数字，第一个数表示小明看中的衣服价格，第二和第三个整数分别表示当天的月份、当天的日期、第四个整数表示是否有优惠券（有优惠券用1表示，无优惠券用0表示）。 注：输入日期保证只有“双11”和“双12”。
输出描述：
一行，小明实际花的钱数（保留两位小数）。（提示：不要指望商家倒找你钱）*/

//int main()
//{
//	int mon, day, test;
//	float money, prise;
//	scanf("%f %d %d %d", &prise, &mon, &day, &test);
//	if (mon == 11 && day == 11)
//	{
//		if (test)
//			money = prise * 0.7 - 50;
//		else
//			money = prise * 0.7;
//	}
//	if (mon == 12 && day == 12)
//	{
//		if (test)
//			money = prise * 0.8 - 50;
//		else
//			money = prise * 0.8;
//	}
//	if (money <= 0)
//		printf("%.2f", 0.00);
//	else
//		printf("%.2f", money);
//	return 0;
//}

////   day 7 3/10     杨辉三角形


//int main()
//{
//	int arr[30][30] = {1};
//	int n ,i, j;
//	scanf("%d", &n);
//	system("cls");
//	for (i = 1; i <= n; i++)
//	{
//		arr[i][0] = 1;
//		for (j = 1; j <= i; j++)
//		{
//			arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
//		}
//	}
//	for (i = 0; i <= n; i++)
//	{
//		for (j = 0; j <= i; j++)
//		{
//			printf("%d ", arr[i][j]);
//		}
//		printf("\n");
//	}
//
//	return 0;
//}


//void swap_char(char* str)
//{
//	int i = 0;
//	assert(str);  //判断str是不是空字符串
//	char* left = str;
//	char* right = str + strlen(str) - 1;
//												//	char* left = str;
//												//	char* right = str + len - 1;
//												//	while (left < right)
//												//	{
//												//		char tmp = *left;
//												//		*left = *right;
//												//		*right = tmp;
//												//		left++;
//												//		right--;
//												//	}
//	while (left < right)
//	{
//		char tmp = *left;
//		*left = *right;
//		*right = tmp;
//		left++;
//		right--;
//
//
//	}
//}
//
//int main()
//{
//	char str[1001];
//	gets(str);
//	printf("%s\n",str);
//
//	swap_char(str);
//	printf("%s\n",str);
//
//	return 0;
//}

//   day 3/11 
// 
// 
// 
// 
    /////                                               模拟实现strcpy
//char* my_strcpy(char* dest,const char* src)
//{
//	assert(src);
//	char* ret = dest;
//	while (*dest++ = *src++)
//	{
//		;
//	}
//	return ret;
//}
//int main()
//{
//	char arr1[] = "hehe";
//	char arr2[20] = {0};
//	printf("%s", my_strcpy(arr2, arr1));
//	return 0;
//}


//
////                                                  模拟实现strcat   追加
//
//char* my_strcat(char* dest, const char* src)
//{
//	assert(dest && src);
//	char* ret = dest;
//	while (*dest != '\0')
//	{
//		dest++;
//	}
//	while (*dest++ = *src++);
//	return ret;
//
//}
//int main()
//{
//	char arr1[20] = "Hello ";
//	char arr2[20] = "world";
//	printf("%s", my_strcat(arr1, arr2));
//	return 0;
//}



//                     day 3/12

//                                            模拟实现strlen
//int my_strlen(char* str)
//{
//	//int cont = 0;
//	//while (*str++)
//	//{
//	//	cont++;
//	//}
//	//return cont;
//	if (*str != '\0')
//		return(1 + my_strlen(str + 1));
//	else
//		return 0;
//
//}
//
//int main()
//{
//	
//	char str[10001];
//	//input(str);
//	gets(str);
//	assert(str);
//	int len =my_strlen(str);
//	printf("%d ", len);
//	return 0;
//}

//                   //       strstr
//char* my_strstr(const char* str1, const char* str2)
//{
//    char* s1 = NULL;
//    char* s2 = NULL;
//    char* cp = (char*)str1;
//    while (*cp)
//    {
//        s1 = cp;
//        s2 = (char*)str2;
//        while (*s1 && *s2 && *s1 == *s2)
//        {
//            s1++;
//            s2++;
//        }
//        if (*s2 == '\0')
//        {
//            return cp;
//        }
//        cp++;
//    }
//    return NULL;
//}
//
//int main()
//{
//    char arr1[] = "abcdefghi";
//    char arr2[] = "f";
//    char* p = my_strstr(arr1, arr2);
//    if (p == NULL)
//    {
//        printf("找不到\n");
//    }
//    else
//    {
//        printf("%s\n", p);
//    }
//    return 0;
//}



//               day 3/13         n n 乘法表

//int main()
//{
//    int i, j,n = 0;
//    scanf("%d", &n);
//    for (i = 1; i <= n; i++)
//    {
//        for (j = 1; j <= i; j++)
//        {
//            printf("%d*%d =%-3d  ", i, j, (i * j));
//        }
//        printf("\n");
//    }
//    return 0;
//}





//                             3/16           memmove模拟实现
//void* my_memmove(void* dest, const void* src, size_t num)
//{
//    void* ret = dest;
//    if (dest < src)
//    {
//        while (num--)
//        {
//            *((char*)dest) = *((char*)src);
//            dest = (char*)dest + 1;
//            src = (char*)src + 1;
//
//        }
//    }
//    else
//    {
//        while (num--)
//        {
//            *(((char*)dest) + num) = *(((char*)src) + num);
//        }
//    }
//    return ret;
//}
//int main()
//{
//    int arr1[] = { 1,2,3,4,5,6,7,8,9,10 };
//    my_memmove(arr1 + 2, arr1, 20);
//    int i = 0;
//    for (i = 0; i < 10; i++)
//    {
//        printf("%d ", arr1[i]);
//    }
//    return 0;
//}


//                                        3/17
//题目：
//输入一个整数数组，实现一个函数，
//来调整该数组中数字的顺序使得数组中所有的奇数位于数组的前半部分，
//所有偶数位于数组的后半部分。
//void tiao_zheng(int* arr, int sz)
//{
//    int left = 0;
//    int right = sz - 1;
//    while (left < right)
//    {
//        while ((left < right) && arr[left] % 2 == 1)
//        {
//            left++;
//        }
//        while ((left < right) && arr[right] % 2 == 0)
//        {
//            right--;
//        }
//        if (left < right)
//        {
//            int tmp = arr[left];
//            arr[left] = arr[right];
//            arr[right] = tmp;
//            left++; right--;
//        }
//
//    }
//
//}
//
//int main()
//{
//    int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    tiao_zheng(arr, sz);
//    for (int i = 0; i < sz; i++)
//    {
//        //scanf("%d", arr);
//        printf("%d ", arr[i]);
//    }
//    return 0;
//}


            //                   3/18   打印杨辉三角
//int main()
//{
//    int arr[30][30] = { 1 };
//    int i, n, j;
//    scanf("%d", &n);
//    system("cls");
//    for (i = 1; i <= n; i++)
//    {
//        arr[i][0] = 1;
//        for (j = 1; j <= i; j++)
//        {
//            arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
//        }
//    }
//    for (i = 0; i <= n; i++)
//    {
//        for (j = 0; j <= i; j++)
//        {
//            printf("%d ", arr[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}



//             3-18         字符串左旋
 //                                    实现一个函数，可以左旋字符串中的k个字符。


/*
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDA*/
//void left_move(char arr[], int n)
//{
//    int len = strlen(arr);
//    int i, j ;
//    i = 0;
//    while(i < n)
//    {
//        char tmp = arr[0];
//        for (j = 0; j <= len - 1; j++)
//        {
//            arr[j] = arr[j + 1];
//        }
//        arr[len - 1] = tmp;
//        i++;
//    }
//}
//
//int main()
//{
//    char arr[] = "abcdef";
//    int k = 0;
//    scanf("%d", &k);
//    left_move(arr, k);
//    printf("%s\n", arr);
//    return 0;
//}



//                                                3-22
////给你一个下标从 0 开始的字符串 ，字符串只包含小写英文字母。你需要选择 一个 下标并 删除 下标处的字符，使得 中剩余每个字母出现 频率 相同。wordword
//
//如果删除一个字母后， 中剩余所有字母的出现频率都相同，那么返回  ，否则返回  。wordtruefalse
//
//注意：
//
//字母 的 频率 是这个字母在字符串中出现的次数。x
//你 必须 恰好删除一个字母，不能一个字母都不删除。


//int main()
//{
//    char world[101] = { 0 };
//    scanf("%s", world);
//    int len = strlen(world);
//    int i, j, n = 0;
//
//    for (i = 0; i < len; i++)
//    {
//        
//        for (j = i + 1; j < len; j++)
//        {
//            if (world[i] == world[j])
//                n++;
//        }
//        if (n >= 2)
//            break;
//    }
//    if (n < 2)
//        printf("true");
//    else
//        printf("false");
//    return 0;
//}


//                         3-24
//int divide(int a, int b)
//{
//    int truncate = 0;
//    int tap = 0;
//    while (a >= b && b > 0)
//    {
//        a -= b;
//        truncate++;
//        tap = 1;
//    }
//    if (tap)
//        return truncate;
//    while (a<b && a>-b && b > 0)
//    {
//        truncate = 0;
//        return truncate;
//    }
//    while (a <= b && b < 0)
//    {
//        a += b;
//        truncate++;
//        tap = 1;
//    }
//    if (tap)
//        return truncate;
//}
//int* runningSum(int* nums, int numsSize, int* returnSize) {
//    *returnSize = numsSize;
//    int i = 0;
//    for (i = 1; i < numsSize; i++)
//    {
//        nums[i] = nums[i - 1] + nums[i];
//    }
//    return nums;
//}
//int main()
//{
//    int a, b, num = 0;
//    scanf("%d %d", &a, &b);
//    num = divide(a, b);
//    printf("%d", num);
//    return 0;
//}


//                 3 - 28
/*一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
例如：
有数组的元素是：1，2，3，4，5，1，2，3，4，6
只有5和6只出现1次，要找出5和6.*/

//int main()
//{
//    int arr[] = {1, 2 ,3, 4, 5, 1, 2, 3, 4, 6};
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    int count, i, j = 0;
//    for (i = 0; i < sz ; i++)
//    {
//        count = 0;
//        for (j = 0; j < sz ; j++)
//        {
//            if (arr[i] == arr[j])
//                count++;
//        }
//        if (count == 1)
//            printf("%d ", arr[i]);
//    }
//    return 0;
//}
//
//void bubble_short(int arr[], int sz)
//{
//	int tmp = 1;
//	int i, j = 0;
//	for (i = 0; i < sz; i++)
//	{
//		for (j = 0; j < sz - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				tmp = arr[j];
//				arr[j] = arr[j + 1];
//				arr[j + 1] = tmp;
//				tmp = 0;
//			}
//		}
//		if (tmp)
//			break;
//	}
//}
//void print(int arr[], int sz)
//{
//	int i = 0;
//	for (i = 0; i < sz; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	printf("\n");
//}
//int main()
//{
//	int arr[10] = { 9,6,7,5,8,4,1,0,2,3 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	printf("排序前：---> ");
//	print(arr, sz);
//	bubble_short(arr, sz);
//	printf("排序后----> ");
//	print(arr, sz);
//	return 0;
//}
//
//#include<iostream>
//#include<cstdio>
//#include<cstdlib>
//#include<cmath>
//    int i, j, t, distn[837], num[837];
//    double
//        x[837], y[837], a[1879], b[1879], dist[837], c, d[837][1879], p[837], r, sum[837];
//int main()
//{
//    freopen("data.txt", "r", stdin);
//    freopen("最短距离 2.out", "w", stdout);
//    for (i = 1; i <= 835; i++)
//        scanf("%lf%lf%d%lf", &x[i], &y[i], &t, &p[i]);
//    for (i = 1; i <= 1877; i++)
//        scanf("%lf%lf%d", &a[i], &b[i], &t);
//    for (i = 1; i <= 835; i++)
//    {
//        sum[i] = 0;
//    }
//    for (r = 0.01; r < 0.06; r += 0.00001)
//    {
//        for (i = 1; i <= 835; i++)
//        {
//            num[i] = 0;
//            dist[i] = 100;
//            for (j = 1; j <= 1877; j++)
//            {
//                d[i][j] = sqrt(0.16 * (x[i] - a[j]) * (x[i] - a[j]) + 1.2769 * (y[i] - b[j]) * (y[i] - b[j]
//                    ));
//                // c=acos(cos(x[i])*cos(a[j])*cos(y[i]-b[j])-sin(x[i])*sin(a[j]));
//                if (d[i][j] < dist[i])
//                {
//                    dist[i] = d[i][j];
//                    distn[i] = j;
//                }
//                if (d[i][j] < r)num[i]++;
//            }
//            sum[i] += (double)num[i] / (r * r);
//        }
//    }
//    for (i = 1; i <= 835; i++)
//    {
//        printf("%d %.10lf %d %d %.16lf %.16f %.16lf %.16lf %.1lf %.16lf",i,dist[i],num[i],distn[i],x[i],y[i],a[distn[i]],b[distn[i]],p[i],(double)sum[i] / 5000);
//            if (y[i] < 113.5)printf("1\n");
//            else printf("2\n");
//    }
//    double ave = 0;
//    for (i = 1; i <= 835; i++)
//        ave += dist[i];
//    ave /= 835;
//    printf("%lf\n", ave);
//    return 0;
//}



//void My_strncpy(const char* arr1, char* arr2, int n)
//{
//	int i = 0;
//	for (i = 0; i < n; i++)
//	{
//		arr2[i] = arr1[i];
//	}
//}
//int main()
//{
//	int n, i = 0;
//	char arr1[100] = { 0 };
//	char arr2[100] = { 0 };
//	printf("请输入要复制的字符串：>");
//	gets(arr1);
//	printf("请输入要复制的字符个数n >");
//	scanf("%d", &n);
//	My_strncpy(arr1, arr2, n);
//	printf("复制的字符串是：%s", arr2);
//	return 0;
//
//}


//4-6            模拟实现strncat
//void My_strncat(char* arr1, const char* arr2, int sz1, int sz2)
//{
//    int i = sz1-1;
//    int j = 0;
//    for (i; i < sz1 + sz2; i++)
//    {
//        arr1[i] = arr2[j];
//        j++;
//    }
//
//}
// 
// 




//                           模拟实现strncat
//char* My_strncat(char* dest, const char* src, size_t n)
//{
//    assert(dest);
//    assert(src);
//
//    char* ret = dest;
//    while (*dest)
//    {
//        dest++;
//    }
//    while (n--)
//    {
//        *dest++ = *src++;
//    }
//    *dest = '\0';
//    return ret;
//}
//int main()
//{
//    /*char arr1[100] = {0};*/
//    char arr1[100] = "abcdef Hello world";
//    char arr2[] = "!!";
//    /*int sz1 = 19;
//    int sz2 = sizeof(arr2);*/
//    My_strncat(arr1, arr2, 1);
//    printf("%s\n", arr1);
//    system("pause");
//    return 0;
//}

//对于一个较大的整数 N(1 <= N <= 2, 000, 000, 000)
//比如 980364535，我们常常需要一位一位数这个数字是几位数，但是如果在这 个数字每三位加一个逗号，它会变得更加易于朗读。
//因此，这个数字加上逗号成如下的模样：980, 364, 535请写一个程序帮她完成这件事情

//int main()
//{
//    int i = 980364535;
//    int k = i;
//    int arr[20] = { 0 };
//    int j, n = 0;
//    j = 0;
//    while (k)
//    {
//        i = k % 10;
//        k /= 10;
//        arr[j] = i;
//        n++; j++;
//    }
//    while (n--)
//    {
//        printf("%d", arr[n]);
//        
//        if ((++k % 3 == 0) && (n != 0) && (k!=0))
//        {
//
//            printf(",");
//        }
//    }
//    return 0;
//}




//                冒泡排序
//void boble_short(int arr[], int sz)
//{
    //int i, j = 0;
    //int flag = 1;
    //for (i = 0; i < sz; i++)
    //{
    //    for (j = 0; j < sz - 1 - i; j++)
    //    {
    //        if (arr[j] < arr[j + 1])
    //        {
    //            flag = 0;
    //            int tmp = arr[j];
    //            arr[j] = arr[j + 1];
    //            arr[j + 1] = tmp;
    //        }
    //        if (flag)
    //            break;
    //    }
    //    if (flag)
    //        break;
    //}
//}
//void print(int arr[], int sz)
//{
//    int i = 0;
//    for (i = 0; i < sz; i++)
//        printf("%d ", arr[i]);
//}
//int main()
//{
//    int arr[] = { 4, 5, 1, 7, 2, 0, 6, 3, 9, 8 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    boble_short(arr, sz);
//    print(arr, sz);
//    return 0;
//}

//#define SWAP(n) (((n&0xaaaaaaaa)>>1)+((n&0x55555555)<<1))
//int main()
//{
//
//    int n = SWAP(10);
//    printf("%d\n", n);
//    return 0;
//}


////                                            模拟实现atoi
//enum State
//{
//    VALID,
//    INVALID
//};
//enum State s = INVALID;//非法的状态
//int My_atoi(const char* str)
//{
//    //空指针
//    assert(str);
//    //空字符串
//    if (*str == '\0')
//        return 0;
//    // + -
//    int flag = 1;
//    if (*str == '+')
//    {
//        flag = 1;
//        str++;
//    }
//    else if (*str == '-')
//    {
//        flag = -1;
//        str++;
//    }
//    long long ret = 0;
//    while (*str)
//    {
//        if (isdigit(*str))
//        {
//            ret = ret * 10 + flag * (*str - '0');
//            if (ret > INT_MAX || ret < INT_MIN)
//            {
//                return (int)ret;
//            }
//        }
//        else
//        {
//            return (int)ret;
//        }
//        str++;
//    }
//    if (*str == '\0')
//    {
//        s = VALID;
//    }
//    return ret;
//
//}
//int main()
//{
//    //char a = "";
//    //scanf("%s", a);
//    int n = My_atoi("1234");
//    // printf("%d", n);
//    if (s == INVALID)
//    {
//        printf("转换非法：%d", n);
//    }
//    else
//        printf("合法转换：%d", n);  
//
//    return 0;
//}





//char** fizzBuzz(int n, int* returnSize) {
//    char** answer = (char**)malloc((sizeof(char*) * (n)));
//    char* arr = (char*)malloc(sizeof(char) * n * 9);
//    *returnSize = n;
//    int i, j = 0;
//    for (i = 0; i < n; i++)
//    {
//        answer[i] = &arr[9 * i];
//    }
//    for (i = 1; i <= n; i++)
//    {
//        if (i % 3 == 0 && i % 5 == 0)
//            strcpy(answer[i - 1], "FizzBuzz");
//        else if (i % 3 == 0)
//            strcpy(answer[i - 1], "Fizz");
//        else if (i % 5 == 0)
//            strcpy(answer[i - 1], "Buzz");
//        else
//            sprintf(answer[i - 1], "%d", i);
//        printf("answer[%d]=%s\n", i, answer[i - 1]);
//    }
//    return answer;
//}



//
////                                                                              4-12
//void rotate1(int* nums, int numsSize, int k) {
//    //if (k % 2 == 0 )
//    //{
//    //    while (k)
//    //    {
//    //        int i, j, a = 0;
//    //        i = numsSize - 1;
//    //        j = nums[i];
//    //        a = nums[i - 1];
//    //        for (i; i > 2; i -= 2)
//    //        {
//    //            nums[i] = nums[i - 1];
//    //            nums[i - 1] = nums[i - 2];
//
//    //        }
//    //        nums[1] = j;
//    //        nums[0] = a;
//    //       
//    //        k -= 2;
//    //    }
//    //}
//        while (k--)
//        {
//        int i, j = 0;
//        i = numsSize - 1;
//        j = nums[i];
//        for (i; i > 0; i--)
//        nums[0] = j;
//    }
//    
//
//}
//
//
//void rotate(int* nums, int numsSize, int k) 
//{
//    int newArr[100000];
//    for (int i = 0; i < numsSize; ++i) {
//        newArr[(i + k) % numsSize] = nums[i];
//    }
//    for (int i = 0; i < numsSize; ++i) {
//        nums[i] = newArr[i];
//    }
//}
////int main()
////{
////    int nums[] = { 1, 2, 4, 1, 6, 8, 35, 33, 11, 66, 88, 99, 111, 222, 3 };
////    int sz = sizeof(nums) / sizeof(nums[0]);
////    int k = 8;
////    rotate(nums, sz, 8);
////    for (int i = 0; i < sz; i++)
////    {
////        printf("%d, ", nums[i]);
////    }
////    return 0;
////}
//
//int missingNumber(int* nums, int numsSize) {
//    int x = (1 + numsSize) * numsSize / 2;
//    for (int i = 0; i < numsSize; i++)
//    {
//        x = x - nums[i];
//    }
//    return x;
//
//}
//
//
//int missingNumber(int* nums, int numsSize) {
//    int x = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        x ^= nums[i];
//    }
//    for (int i = 0; i <= numsSize; i++)
//    {
//        x ^= i;
//    }
//    return x;
//}
//
//int removeElement(int* nums, int numsSize, int val) {
//    int left = 0, right = numsSize;
//    while (left < right) {
//        if (nums[left] == val) {
//            nums[left] = nums[right - 1];
//            right--;
//        }
//        else {
//            left++;
//        }
//    }
//    return left;
//}